#include <bits/stdc++.h>
using namespace std;
class Node{
public:
    int data;
    Node* next;
    Node(int d,Node* p)
    {
        data = d;
        next = p;
    }
};
Node* FindKthToTail(Node* head, unsigned int k)
{
    //k=0或者指针为空时可能导致崩溃
    if(head == nullptr||k==0)
        return nullptr;
    int i=0;
    Node* p = head;
    Node* q = head;
    Node* finded_node = new Node(0,nullptr);
    for(int j = 0;j<k;j++)
    {
        //每一步都必须判断是不是走到了空指针位置
        if(p!= nullptr)
            p = p->next;
        else
            return nullptr;
    }
    while(p)
    {
        p = p->next;
        q = q->next;
    }

    finded_node->data = q->data;
    finded_node->next = q->next;
    return finded_node;

}
int main() {
    Node* root = new Node(1, nullptr);
    Node* a = new Node(3, nullptr);
    Node* b = new Node(5, nullptr);
    Node* c = new Node(7, nullptr);
    Node* d = new Node(9, nullptr);

    root->next = a;
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = nullptr;
    Node* find_node;
    find_node = FindKthToTail(root,3);
    cout<<find_node->data<<" ";
    delete root;
    delete a;
    delete b;
    delete c;
    delete d;
    delete find_node;

    return 0;
}
